public class Test5 {
    public static void main(String[] args) {
        char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        String word = "ABCCED";
        exist(board, word);
    }

    static int m, n;
    static boolean[][] check;
    static char[] word;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    public static boolean exist(char[][] board, String _word) {
        m = board.length;
        n = board[0].length;
        check = new boolean[m][n];
        word = _word.toCharArray();
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == word[0]) {
                    check[i][j] = true;
                    if(dfs(board, i, j, 1)) return true;
                    check[i][j] = false;
                }
            }
        }
        return false;
    }
    public static boolean dfs(char[][] board, int row, int col, int pos) {
        if(pos == word.length) {
            return true;
        }
        for(int i = 0; i < 4; i++) {
            int x = row + dx[i];
            int y = col + dy[i];
            if(x >= 0 && x < m && y >= 0 && y < n) {
                if(check[x][y] == false && board[x][y] == word[pos]) {
                    check[x][y] = true;
//                    dfs(board, x, y, pos + 1);
                    if(dfs(board, x, y, pos + 1))
                        return true;
                    check[x][y] = false;
                }
            }
        }
        return false;
    }
}
